#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (n < *pi)
		return NULL;
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	root->_data = a[(*pi)++];
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);

	return root;
}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;

	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*root);
	*root = NULL;
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	int iz = BinaryTreeLeafSize(root->_left);
	int iy = BinaryTreeLeafSize(root->_right);

	return (root->_left == NULL) && (root->_right == NULL) ? 0 + iz + iy : 1 + iz + iy;
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->_left, k-1) + BinaryTreeLevelKSize(root->_right, k-1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;

	BTNode* pz = BinaryTreeFind(root->_left, x);
	if (pz)
		return pz;

	BTNode* py = BinaryTreeFind(root->_right, x);
	if (py)
		return py;

	return NULL;
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
		return;

	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	assert(root);
	Queue q;
	QueInit(&q);

	QuePush(&q, root);
	while (!QueEmpty(&q))
	{
		BTNode* pnode = QueFront(&q);
		QuePop(&q);

		if (pnode)
		{
			printf("%c ", pnode->_data);
			QuePush(&q, pnode->_left);
			QuePush(&q, pnode->_right);
		}
	}

	QueDestory(&q);
}

int BinaryTreeComplete(BTNode* root)
{
	assert(root);
	Queue q;
	Queue p;
	QueInit(&q);
	QueInit(&p);
	QuePush(&q, root);
	while (!QueEmpty(&q))
	{
		BTNode* pnode = QueFront(&q);
		QuePop(&q);

		if (pnode)
		{
			QuePush(&q, pnode->_left);
			QuePush(&q, pnode->_right);
		}
		QuePush(&p, pnode);
	}

	QueDestory(&q);
	int size = BinaryTreeSize(root);
	while (size--)
	{
		BTNode* pnode = QueFront(&p);
		QuePop(&p);
		if (pnode == NULL)
			return 0;
	}
	QueDestory(&p);
	return 1;
}
